\noindent
A substantial portion of our
experimental capital  was spent on the study of the evolution of boolean argument functions. There are two reasons for this:
\begin{enumerate}
\item Boolean formulas can be used to compute quite complicated functions, and  it is natural to consider their learnability
\item Our first motivator for using \SF{} as an underlying representation scheme was its expressive power. In this case, we demonstrate the advantage of the system as a GP language by evolving all functions in this section without defining  any
    terminals that need to be evaluated outside the system. Instead, we used a terminal set exclusively composed
    of names for \SF{} pure abstract terms and types (expressions that do not contain constants). We've already described the representation of Boolean functions as pure abstraction in section \ref{SFBoolType}. In this section, we make use of this encoding for all the problems described.
\end{enumerate}
All results in this section were obtained using context BooleanDef (\ref{BooleanDef})
\begin{context}[h]
\begin{verbatim}
/*Unique type defined as pure abstraction */
TyBool = TT X . X -> X ->X;

/*The two type constructors               */
true = Lam X . lam x : X . lam y : X . x;
false = Lam X . lam x : X . lam y : X . y;
\end{verbatim}
\caption{$\mathit{BooleanDef}$}\label{BooleanDef}
\end{context}



\subsection{The $not$ Boolean Function}
\noindent
In this problem, we evolve a program that evolves a one argument $not$ function using the following list of test cases:
\begin{verbatim}
Arg (TyBool),Result (TyBool)
true, false
false, true
\end{verbatim}
\noindent
when using the following set of initial variables:
\begin{verbatim}
    maxGeneComp = 50
    maxComp = 1000
    geneDifference = 12
    populationDefaultSize = 10
\end{verbatim}
and performing 100 runs:
\begin{itemize}
\item 42\% of the runs discover a solution on the first generation
\item 23\% of the runs discover a solution on the second generation
\item 17\% of the runs discover a solution on the third generation
\item 18\% of the runs discover a solution on the fourth generation
\end{itemize}
Each generation after the first one destroys 3 live genotypes and evaluates
3 new genotypes, so by the fourth generation a maximum of 19 genotypes have been evaluated with a 100\%
chance of finding a solution. However, simply running a first generation (10 evaluations) twice for a
total of 20 generations only produces an 84\% chance of finding a solution. This indicates that
the discovery process is not random. The maximum fitness score is 2 (as there are two test cases). The average fitness on:
\begin{itemize}
\item Generation 1 is 0.39
\item Generation 2 is  0.625
\item Generation 3 is 0.84
\item Generation 4 is 0.98
\end{itemize}
Which demonstrates that there is an increase of fitness with the passing of generations.

\subsubsection{Solution example}
As mentioned, the system always finds a solution (within 4 generations). One of the evolved one allele-species solutions was:
\begin{verbatim}
(/*  Gene = (TT A. A-> A-> A)-> (TT O. O-> O-> O)-- ID = 5*/
     lam x:TT A. A-> A-> A.x [TT K. K-> K-> K]
        (Lam O.lam m:O.lam s:O.s)
        (Lam O.lam c:O.lam r:O.c))
\end{verbatim}
which normalizes to:
\begin{equation}\label{notSolutionPrgram}
\la{e}{TyBool}.e\ [TyBool]\ (false)\ (true)
\end{equation}
The program belongs to the species illustrated by figure \ref{SpeciesNotSolution}.
\begin{figure}[h]
\centering \epsfig{file=SpeciesNotSolution.eps, width=50mm}
\caption{Species to which the example program ($not$ function) that normalizes to \ref{notSolutionPrgram} belongs}
\label{SpeciesNotSolution}
\end{figure}

\subsection{The $and$ Boolean Function}
For this problem, the system evolves a two argument $and$ function
using the following list of test cases:
\begin{verbatim}
Arg1(TyBool),Arg2(TyBool),Result(TyBool)
true, true, true
false, true, false
true, false, false
false, false, false
\end{verbatim}
Using the same variables:
\begin{verbatim}
    maxGeneComp = 50
    maxComp = 1000
    geneDifference = 12
    populationDefaultSize = 10
\end{verbatim}
The system finds a solution (over 100 runs):
\begin{itemize}
\item 8\% of the time on the 1st generation
\item 11\% of the time on the 2nd generation
\item 33\% of the time on the 3rd generation
\item 36\% of the time  on the 4th generation
\item 12\% of the time  on the 5th generation
\end{itemize}
\subsubsection{Solution example}
One of the evolved solutions was:
\begin{small}
\begin{verbatim}
(/* Gene = ((TT W. W-> W-> W)-> (TT I. I-> I-> I)->
                (TT F. F-> F-> F)-> (TT E. E-> E-> E))->
                (TT J. J-> J-> J)-> (TT J. J-> J-> J)->
                (TT U.U-> U-> U)-- ID = 4*/
    lam a:(TT I. I-> I-> I)-> (TT P. P-> P-> P)->
          (TT K. K-> K-> K)-> (TT T. T-> T-> T).
    lam w:TT M. M-> M-> M.a w w)

(/* Gene = (TT K. K-> K-> K)-> (TT J. J-> J-> J)->
            (TT L. L-> L-> L)-> (TT I. I-> I-> I)-- ID = 5*/
    lam w:TT Y. Y-> Y-> Y.
        w [TT U. U-> U-> U]
            (Lam N.lam k:N.lam q:N.q)
            (Lam F.lam k:F.lam j:F.k) [TT E. E-> E-> E])
\end{verbatim}
\end{small}
which simplifies to:
\begin{equation}\label{andSolutionPrgram}
\la{i}{TyBool}.i\ \typ{TyBool}\ false\ true\ \typ{TyBool}\ i
\end{equation}
The program belongs to the species illustrated by figure \ref{SpeciesAndSolution}
\begin{figure}[h]
\centering \epsfig{file=SpeciesAndSolution.eps, width=130mm}
\caption{Species to which the example program ($and$ function) that
normalizes to \ref{andSolutionPrgram} belongs}
\label{SpeciesAndSolution}
\end{figure}

\subsection{The $or$ Boolean Function}
For this problem, our system evolves a two argument $or$ function
using the following list of test cases:
\begin{verbatim}
Arg1(TyBool),Arg2(TyBool),Result(TyBool)
true, true, true
false, true, true
true, false, true
false, false, false
\end{verbatim}
Using the set of variables:
\begin{verbatim}
    maxGeneComp = 50
    maxComp = 1000
    geneDifference = 12
    populationDefaultSize = 10
\end{verbatim}
The system finds a solution (over 100 runs):
\begin{itemize}
\item 3\% of the time on the 1st generation
\item 15\% of the time on the 2nd generation
\item 24\% of the time on the 3rd generation
\item 33\% of the time  on the 4th generation
\item 13\% of the time  on the 5th generation
\item 12\% of the time  on the 6th generation
\end{itemize}

\subsubsection{Solution example}
The system always finds a solution. For example:
\begin{verbatim}
(/* Gene =  (TT R. R-> R)-> (TT V. V-> V-> V)->
            (TT J. J-> J-> J)-> (TT V. V-> V-> V)--ID = 18*/
    lam q:TT S. S-> S.
    lam v:TT P. P-> P-> P.v [TT K. K-> K-> K] v)

(/* Gene = TT G. G-> G-- ID = 0*/
    Lam I.lam k:I.k)
\end{verbatim}
which simplifies  to the ingenuous solution:
\begin{equation}\label{orSolutionPrgram}
\la{i}{TyBool}.i\ \typ{TyBool}\ i
\end{equation}
\noindent
Compare, for example with the more obvious but longer:
\begin{equation}
\la{o}{TyBool}.\la{t}{TyBool}.o\ \typ{TyBool}\ (true)\ t
\end{equation}
The solution program belongs to the species illustrated by figure \ref{SpeciesOrSolution} (this result was obtained on an older version of the system. The symbol `ProgNode' should read `Gene' and `ImplyElim' should read `$\rightarrow$elim').
\begin{figure}[h]
\centering \epsfig{file=SpeciesOrSolution.eps, width=90mm}
\caption{Species to which the example program ($or$ function) that normalizes to \ref{orSolutionPrgram} belongs}
\label{SpeciesOrSolution}
\end{figure}

\subsection{The $xor$ Boolean Function}
The preceding functions were relatively easier to evolve than an $xor$. To evolve $xor$, we use:
\begin{verbatim}
    maxGeneComp = 50
    maxComp = 5000
    geneDifference = 12
    populationDefaultSize = 100
\end{verbatim}
Over a set of 100 runs, we obtain a solution in
\begin{itemize}
\item 2\% of the time on the 1st generation
\item 10\% of the time on the 2nd generation
\item 24\% of the time on the 3rd generation
\item 23\% of the time  on the 4th generation
\item 17\% of the time  on the 5th generation
\item 13\% of the time  on the 6th generation
\item 11\% of the time  on the 7th generation
\end{itemize}
\subsubsection{Solution example}
The system always find a solution (but with more effort):
{\small
\begin{verbatim}
(((/* Gene = (TT Y. Y-> Y-> Y)->
             (TT M. (M-> M)-> (TT D. D-> D-> D)-> M-> M)->
             ((TT O. O-> O-> O)-> (TT R. R-> R-> R))->
             (TT T. T-> T-> T)->
             (TT S. S-> S-> S)->
             (TT P. P-> P-> P)-- ID = 0*/
    lam q:TT Y. Y-> Y-> Y.
    lam d:TT I. (I-> I)-> (TT V. V-> V-> V)-> I-> I.d [TT O. O-> O-> O])

(/* Gene = TT P. P-> P-> P-- ID = 1*/
    Lam L.lam k:L.lam n:L.k))

(/* Gene = TT N. (N-> N)-> (TT U. U-> U-> U)-> N-> N-- ID = 0*/
    Lam K.lam n:K->K.lam h:TT N. N-> N-> N.lam c:K.h [K] (n c) c))

(/* Gene = (TT Y. Y-> Y-> Y)-> (TT J. J-> J-> J)-- ID = 4*/
    lam r:TT D. D-> D-> D.
        r [TT D. D->D-> D]
            (Lam K.lam s:K.lam w:K.w)
            (Lam S.lam n:S.lam x:S.n))
 \end{verbatim}}
 \noindent
 which simplifies  to the term:
 \begin{equation}\label{xorSolutionPrgram}
\la{j}{TyBool}.\la{p}{TyBool}.j\ \typ{TyBool}\ (p\ \typ{TyBool}\ (false)\ (true))\ p
\end{equation}
The program belongs to the species illustrated by figure \ref{SpeciesXOrSolution}
\begin{figure}[h]
\centering \epsfig{file=SpeciesXOrSolution.eps, width=140mm}
\caption{Species to which the example program ($xor$ function) that
normalizes to \ref{xorSolutionPrgram} belongs}
\label{SpeciesXOrSolution}
\end{figure}


\subsection{The Half-adder Boolean Function}
\begin{figure}[H]
\centering \epsfig{file=halfaddercirc.eps, width=100mm} \caption{A
half-adder circuit} \label{halfaddercirc}
\end{figure}
\noindent
In this problem, we evolve a two argument $half$-$adder$
function. The half-adder circuit produces two output: The carry and
the sum resulting from the addition of the two 1-bit arguments. As
an electronic circuit, it might be built as per schema of figure
\ref{halfaddercirc}.
we use:
\begin{verbatim}
    maxGeneComp = 50
    maxComp = 5000
    geneDifference = 12
    populationDefaultSize = 1000
\end{verbatim}
\noindent
We evolved the function using the following list of test cases:
{\small
\begin{verbatim}
Arg1(TyBool),Arg2(TyBool),Result(TT X .TyBool->TyBool->X)
true,true, Lam X . lam x : TyBool->TyBool->X.x true false
false, true, Lam X . lam x : TyBool->TyBool->X.x false true
true, false, Lam X . lam x : TyBool->TyBool->X.x false true
false, false, Lam X .lam x : TyBool->TyBool->X.x false false
\end{verbatim}}

\noindent
in which the function's output is encoded as a pair (the
first element is the carry, the second is the sum). We give no
indication to the system as to what the structure of a pair is, or
how to form one, beyond what is encoded in the test cases. The
context is sill completely defined by context \ref{BooleanDef}. We get a solution
within 9 generations 89\% of the time.
\subsubsection{Solution example}
An example solution:
\begin{samepage}
{\small
\begin{verbatim}
(/* Gene = ((TT V. V-> V-> V)-> (TT O. O-> O-> O)->
    (TT O. O-> O-> O))-> (TT R. R-> R-> R)->
    (TT W. W-> W-> W)-> (TT V. (TyBool-> TyBool-> V)-> V)-- ID = 0*/

    lam m:TyBool-> TyBool-> TyBool.
    lam y:TyBool.lam j:TyBool.
    Lam M.lam u:TyBool-> TyBool-> M.u (y [TT P. P-> P-> P] j y) (m y j))

((/* Gene = ((TT Y. Y-> Y-> Y)-> (TT Y. Y-> Y-> Y))->
            (TT V. V-> V-> V)-> (TT N. N-> N-> N)->
            (TT A. A-> A-> A)-- ID = 0*/

    lam r:(TT X. X->X-> X)-> (TT G. G-> G-> G).
    lam n:TT R. R-> R-> R.
    lam v:TT G. G-> G-> G.n [TT R. R-> R-> R] (r v) v)

(/* Gene = (TT J. J-> J-> J)-> (TT Q. Q-> Q-> Q)-- ID = 18*/

    lam r:TyBool.r [TT U. U-> U-> U]
        (Lam X.lam o:X.lam t:X.t)
        (Lam L.lam c:L.lam h:L.c)))
\end{verbatim}}
\end{samepage}
\noindent
Corresponding to the normalization:
\begin{equation}\label{AAdderSolutionPrgram}
\begin{split}
\la{y}{TyBool}.& \la{e}{TyBool}.\\
&\Pi M.\la{x}{\AT{TyBool}{\AT{TyBool}{M}}}.\\
&x\ (y\ [TyBool]\ e\ y)\ (y\ [TyBool]\ (e\ [TyBool]\ (false)\ (true))\ e)
\end{split}
\end{equation}
The program belongs to the species illustrated by figure \ref{SpeciesAAderSolution}.
\begin{figure}[h]
\centering \epsfig{file=SpeciesAAdderSolution.eps, width=130mm}
\caption{Species to which the example program (half-adder) that
normalizes to \ref{AAdderSolutionPrgram} belongs}
\label{SpeciesAAderSolution}
\end{figure}

